### 解题思路
1.本题采用中心扩散法，时间复杂度O(n方)，空间复杂度O(1)。
2.第一个注意，对aabbaa偶数回文字符串的处理。
我们可以先遍历一次，将相邻相同的字符之间插一个一定不会出现的特殊符号(例如"-")
例子变成a-ab-ba-a,不难发现已经变成奇数回文串了。
3.第二个注意,如果每次回文串拿一个string装着，看似只用了一个变量，但放进字符操作其实都很耗时的，即使方法对也不能AC，一定要通过下标边界来截取子字符串。表示大小的时候注意删去特殊字符的数量。
4.第三个注意，遍历技巧，先处理size<2和全部同一个字符的情况。然后遍历的时候第一个和最后一个就不用考虑了，他们不会成为中心。还有一个小提示:中间往后回文的极限大小只会越来越小，部分情况可以提前break，如下:
if(R-L>=(s.size()-i)*2-1)
            {
                break;
            }

date:20210330 22:45 pm
user:LDC
### 代码

```cpp
//首先采用的是中心扩散法,时间复杂度O(n方)，空间复杂度O(1)，就用了两个变量存下标L,R
class Solution {
public:
    //已知字符串某一个位置，返回以这个位置为中心的最大回文字符串
    bool MAX_i_HuiWen(int i,string s,int&k,int&L,int&R)
    {//写成bool只是方便中断
        if(i==0)
        {
            L=0;
            R=1;
        return 0;
        }


        //先把中间的i元素插入

        L=i;
        R=i+1;
        int j=1;
        //k负责统计特殊字符在本次回文串的出现次数
        if(s[i]=='-')
                {
                    k++;
                }
        //碰到左或右边界就停止延申(用LR也可以表示，但搞太复杂没必要
        while(i-j>=0&&(i+j<=s.size()-1))
        {
            if(s[i-j]==s[i+j])
            {
                if(s[i-j]=='-')
                {
                    k+=2;
                }
            //左边插入i-j
            L--;
            //右边插入i+j
            R++;
            j++;
            }
            else
            {
                break;
            }
        }
        //cout<<k;
       return 1;
    }
    //去掉我添加的特殊符号-
    void delet_ex(string&s)
    {
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='-')
            {
                s.erase(i,1);
                
            }
        }
    }
    //防止全部同一个字符
    bool allthesame(string s)
    {
        for(int i=0;i<s.size();i++)
        {
            if(i>0)
            {
                if(s[i]!=s[i-1])
                {
                    return 0;
                }
            }
        }
        return 1;
    }
    
    string longestPalindrome(string s)
    {
        if(s.size()<2)
        {
            return s;
        }
        if(allthesame(s))
        {
            return s;
        }
        

        int i;
        //对所有相同相邻元素插入特殊字符
        for(i=1;i<s.size();i++)
        {

            if(s[i-1]==s[i])
            {
                //在第i个元素的前面插入
                s.insert(s.begin()+i,'-');
                i++;
            }
        }
  
        //每一个元素尝试成为回文中心，不需要遍历到最后一个
        int k;
        int s1_size=0;//维护最大回文串的大小
        int L,R,L1,R1;

        //至少有两个数字，然后第一个和最后一个都没必要遍历，永远不可能作为中心位
        for(i=1;i<s.size()-1;i++)
        {
            //每轮都对特殊字符做统计
            k=0;
            MAX_i_HuiWen(i,s,k,L,R);
            //减去特殊字符得到真实大小
            if(R-L-k>=s1_size)
            {
                
                s1_size=R-L-k;
                //维护最佳L\R
                L1=L;
                R1=R;
            }
            
            //中间往后回文的极限大只会越来越小
            if(R-L>=(s.size()-i)*2-1)
            {
                break;
            }
        }
        //按边界切割
        s=s.substr(L1,R1-L1);
        //把特殊字符删掉
        delet_ex(s);
        return s;
        
    }
};
```